import math
import random

def assign_cluster(x, c):
    """
    将样本x分配到最近的聚类中心
    参数:
        x: 单个样本(列表或元组)
        c: 聚类中心列表(每个元素为列表或元组)
    返回:
        最近聚类中心的索引
    """
    min_dist = float('inf')
    cluster_idx = 0
    for i, center in enumerate(c):
        # 计算欧氏距离
        dist = math.sqrt(sum((xi - ci)**2 for xi, ci in zip(x, center)))
        if dist < min_dist:
            min_dist = dist
            cluster_idx = i
    return cluster_idx

def Kmeans(data, k, epsilon, iteration):
    """
    K均值聚类算法
    参数:
        data: 数据集(列表，每个元素为样本)
        k: 聚类数量
        epsilon: 中心点变化阈值，小于此值停止迭代
        iteration: 最大迭代次数
    返回:
        centers: 最终聚类中心
        labels: 每个样本的聚类标签
    """
    # 检查输入合法性
    if k <= 0 or k > len(data):
        raise ValueError("k值必须为正且不大于样本数量")
    if epsilon <= 0:
        raise ValueError("epsilon必须为正数")
    if iteration <= 0:
        raise ValueError("迭代次数必须为正")
    
    # 初始化聚类中心(随机选择k个不同样本)
    centers = random.sample(data, k)
    n_features = len(data[0])  # 特征维度
    
    for _ in range(iteration):
        # 分配聚类
        clusters = [[] for _ in range(k)]  # 每个聚类包含的样本
        for x in data:
            idx = assign_cluster(x, centers)
            clusters[idx].append(x)
        
        # 计算新的聚类中心
        new_centers = []
        for cluster in clusters:
            if not cluster:  # 避免空聚类(可根据实际需求调整处理方式)
                new_centers.append(random.choice(data))  # 随机选一个样本作为中心
                continue
            # 计算每个特征的均值
            center = [sum(dim) / len(cluster) for dim in zip(*cluster)]
            new_centers.append(center)
        
        # 计算中心变化量
        total_move = 0.0
        for old, new in zip(centers, new_centers):
            total_move += math.sqrt(sum((o - n)**2 for o, n in zip(old, new)))
        
        # 检查是否收敛
        if total_move < epsilon:
            centers = new_centers
            break
        
        centers = new_centers
    
    # 生成最终标签
    labels = [assign_cluster(x, centers) for x in data]
    return centers, labels